from typing import List


def findSubstring(s: str, words: List[str]) -> List[int]:
    if len(words) == 0:
        return []
    tot = {}
    n = len(s)
    m = len(words)
    w = len(words[0])
    for i in range(len(words)):
        if words[i] in tot:
            tot[words[i]] += 1
        else:
            tot[words[i]] = 1
    i = 0
    res = []
    while i < w:
        cnt = 0
        j = i
        wd = {}
        while j + w <= n:
            if j >= i + w * m:
                word = s[j - w * m: j - w * m + w]
                wd[word] -= 1
                if word in tot and wd[word] < tot[word]:
                    cnt -= 1
            word = s[j: j + w]
            if word in wd:
                wd[word] += 1
            else:
                wd[word] = 1
            if word in tot and wd[word] <= tot[word]:
                cnt += 1
            if m == cnt:
                res.append(j - w * (m - 1))
            j += w
        i += 1
    return res


s = "barfoothefoobarman"
words = ["foo","bar"]
print(findSubstring(s, words))
